798. 得分最高的最小轮调

算法内容

本文件实现 LeetCode 798「得分最高的最小轮调」。旋转后，如果元素值不大于它的新下标，该元素得 1 分，要求返回得分最高且下标最小的旋转值。

代码使用差分数组记录每个元素在哪些旋转区间内可以得分。对位置 i 的元素 nums[i]，计算它得分的旋转区间 [low, high)，在差分数组中做区间加一；当区间跨过 0 时额外给 diff[0] 加一。最后对差分数组求前缀和，得到每个旋转值的总分，并保留第一次出现的最大值位置。时间复杂度 O(n)，空间复杂度 O(n)。

算法实现

#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    int bestRotation(vector<int>& nums) {
        int len = nums.size();
        vector<int> diff(len, 0);
        for(int i = 0; i < len; i++) {
            int low = (i+1)%len, high = (len + i - nums[i] + 1) % len;
            diff[low]++;
            diff[high]--;
            if(low >= high) {
                diff[0]++;
            }
        }
        int max = 0;
        int cur = 0;
        int pos = 0;
        for(int i = 0; i < len; i++) {
            cur += diff[i];
            if(max < cur) {
                pos = i;
                max = cur;
            }
        }
        return pos;
    }
};